package com.skh.array;

/**
 * 二维数组中的查找
 */
public class Find {

    /*
    题目描述
    在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
    请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     */

    /*
    思路:

    * 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
    * 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
    * 要查找数字比左下角数字小时，上移

    利用二维数组由上到下，由左到右递增的规律，
    那么选取左下角的元素a[row][col]与target进行比较，
    当target小于元素a[row][col]时，那么target必定在元素a所在行的上边,
    即row--；
    当target大于元素a[row][col]时，那么target必定在元素a所在列的右边,
    即col++；
     */
    public boolean find(int target, int [][] array) {
        int row = array.length;
        int col = array[0].length;
        //从左下角开始找
        int i = row-1;
        int j = 0;

        while (i>=0 && j<col) {
            if (target == array[i][j]){
                return true;
            }else if(target > array[i][j]){
                j++; //目标值大,说明在右边,列++
            } else {
                i--; //目标值小,说明在上边,行--
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] arrs = {{}};
        Find find = new Find();
        System.out.println(arrs.length);
        System.out.println(arrs[0].length);
        boolean b = find.find(16, arrs);
        System.out.println("b = " + b);
    }
}
